The present invention relates to digital transmission networks and, more particularly, to networks in which particular data sequences are to be detected and/or eliminated.
An ever increasing number of digital networks utilize telephone long lines to interconnect computers in geographically distant locations. The telephone lines in question include T.sub.1 lines and fiber optic lines. These systems include repeaters which compensate for transmission losses on the lines and receivers associated with various network devices. These repeaters and receivers must remain synchronized with each other. This synchronization is maintained through the detection of the transitions between 1 and 0 bits in the data at each repeater location. If data having long runs of 1s or 0s is sent on such a long line, time synchronization may be lost. This loss of synchronization will jeopardize network integrity, possibly resulting in failure of the entire long line transmission system.
Long runs of 1s or 0s are not a problem in systems carrying only voice data, since there is always enough static on the lines to provide the transitions in question. In addition, consecutive time slots on the T.sub.1 lines are assigned to different users. Hence, no one user can control more than a small fraction of the capacity of the line.
Computer data, however, often includes long runs of 1s and 0s. In addition, advanced digital networks may assign a large fraction of the channel capacity to a single user, thereby allowing a single user sending digital data to force a long string of 1s or 0s onto the transmission lines. As a result, some method of converting such data runs to non-destructive runs for transmission on the long lines is needed. Several prior art techniques have addressed this problem. Some digital networks assemble the user data into packets before transmitting that data on the long lines. In this type of system, overhead bits are added to the user data to guarantee that even if a user transmits all 0s, a run of more than some predetermined number of 0s on the long line is not possible.
such schemes guarantee that no long runs of 0s or 1s are transmitted, they waste transmission capacity. For example, in some T.sub.1 based digital networks, data is transmitted as 8-bit packets in which user data forms 7 bits of the packet and the 8th bit is forced to be a "1". This solution wastes of 1/8th of the capacity of the long line.
A second type of solution to this problem involves scrambling the user data sequence before transmission on the long lines, and then descrambling it upon receipt at the other end. The scrambling algorithm converts long runs of 1s and 0s into sequences that include the requisite density of 1-0 transitions. For example, in one proposed system, each bit of the user data stream is paired with a bit from a scrambling sequence. The pair of bits in question are then added modulo 2 to form a bit of the scrambled output sequence. The scrambling sequence in question consists of a circular list of N bits. That is, bit 1 of the scrambling sequence is added to bit 1 of the user data to form bit 1 of the scrambler output. Then bit 2 of the scrambling sequence is added to bit 2 of the user data to form bit 2 of the scrambler output, and so on until bit N is used. Then the scrambling sequence is replayed, i.e., bit 1 of the scrambling sequence is added to bit N+1 of the user data to form bit N+1 of the scrambler output.
Although this system prevents long runs of 1s and 0s in the user data from being repeated on the long lines, a user, particularly a malicious one, can still cause long runs of 1s and 0s to be sent on the long lines. If the user data contains a bit sequence which matches that of the scrambling sequence paired thereto, a run of 0s will be generated. Similarly, if the user data contains a bit sequence that matches the 1s complement of the scrambling sequence, a run of 1s will be generated.
The probability that a string of 1s or 0s long enough to destroy synchronization will occur depends on how long a sequence the system can tolerate. For example, in fiber optic long lines, runs of a maximum of 60 0s can be tolerated. In this case, one would need a user sequence containing a 60-bit sub-sequence of the scrambling sequence to destroy synchronization. Such a sequence will be referred to as an illegal sequence in the following discussion. If all user data sequences were equally likely, it would take hundreds of years, on average, to encounter an illegal sequence.
Unfortunately, not all user data sequences are equally likely. Computer and telecommunications systems have long been plagued by malicious users who attempt to disable the systems. If such an individual was privy to the scrambling sequence, he could disable the system by sending the sequence in question in such a manner that it would be likely to match up with the scrambling sequence, thus causing a run of 0s or 1s to be placed on the long lines. Given the number of individuals involved in maintaining telecommunications systems, it is unlikely that the scrambling sequence could be kept secret; hence, some means of preventing system sabotage by malicious individuals sending the scrambling sequence is needed.
One proposed solution to this problem is to use a self-synchronizing pre-scrambling scheme in which the sequence leading to a run of 0s or 1s of the critical length can not be predicted. For example, a prescrambler is placed in series with each of the above described scramblers. The pre-scrambler executes an algorithm which depends upon the contents of the prescrambler prior to the arrival of the user data sequence. The encrypted pre-scrambled data is then scrambled a second time by a standard network scrambler, transmitted on the long line, and descrambled by a network descrambler at the end of the long line. The data is then further descrambled by a second decoder which decrypts the code utilized by the unpredictable pre-scrambler.
This solution has a number of drawbacks.
First, the pre-scrambler and corresponding decryption circuitry must be installed in a number of transmitters and receivers in the network. This significantly increases the cost of the network. Second, transmission errors may be multiplied by the decryption circuitry unless error-correcting bits are included in the encrypted data. The error-correcting bits utilize transmission capacity which could otherwise carry user data; hence, the overall capacity of the system is reduced.
Third, this solution does not permit the detection of illegal sequences. Ideally, one would like to detect an illegal sequence at its point of origin and then sound an alarm. The possibility of capture would then discourage malicious individuals from attempting to disable the telecommunications system. The above described pre-scrambling scheme does not test for any specific sequence.
Finally, the potential for a malicious individual or pure chance to generate an illegal sequence is not completely eliminated by the prescrambler. There is always a possibility that the malicious individual, either by chance or by gaining knowledge of the pre-scrambler contents, could cause an illegal sequence to be generated at the output of the pre-scrambler. The result could be a complete failure of the telecommunications system because of loss of synchronization.
Broadly, it is an object of the present invention to provide an apparatus and method for preventing illegal sequences from being transmitted on a telecommunications link.
It is a further object of the present invention to provide a method and apparatus which does not reduce the data carrying capacity of the telecommunications link.
It is another object of the present invention to provide a method and apparatus which does not result in error multiplication in the data transmitted on the telecommunications link.
It is a still further object of the present invention to provide a method and apparatus which guarantees that an illegal sequence can not be generated from any possible input sequence.
It is yet another object of the present invention to provide a method and apparatus that detects illegal sequences.
It is a still another object of the present invention to provide a method and apparatus for sounding an alarm when such an illegal sequence is detected.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.